//
//  ProblemOffer43.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/28.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 43. 1～n 整数中 1 出现的次数
 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

 示例 1：
     输入：n = 12
     输出：5
 示例 2：
     输入：n = 13
     输出：6
 限制：1 <= n < 2^31
 */
@objcMembers class ProblemOffer43: NSObject {
    func solution() {
        print(countDigitOne(12))
        print(countDigitOne(13))
    }
    
    /*
     看十位上的数字，
     1> 假如是0时，例如：2304，我们想求出当十位上变成1时 **0* => **1*，有多少种数字
        前面的有23种可能性： 00 01 02 ... 22
        后面有10种可能性：0～9
        个数 = 23 * 10, 也就是只和前面有关
     2> 假如是1时，例如：2314，我们想求出当十位上变成1时 **1* => **1*，有多少种数字
        前面有24种可能性，但是只有前23个[00..22]是可以*10，最后一个23不完整，他只有5种 0～4，
        个数 = 23 * 10 + 4 + 1，也就是和前面+后面有关
     3> 加入是2～9，例如：2334，我们想求出当十位上变成1时 **3* => **1*，有多少种数字
        前面有有24种可能性，[00..23] * 10
        后面有10种 10～19
        个数 = 23 * 10 + 10 = （23 + 1） * 10
     
     */
    func countDigitOne(_ n: Int) -> Int {
        var digit = 1               // 当前的位数
        var height = n / 10         // 高位
        var low = 0                 // 低位
        var cur = n % 10            // 当前位
     
        var result = 0
        while cur != 0 || height != 0 {
            if cur == 0 {
                result += height * digit
            } else if cur == 1 {
                result += height * digit + low + 1
            } else {
                result += (height + 1) * digit
            }
            
            low += cur * digit
            cur = height % 10
            height /= 10
            digit *= 10
        }
        return result
    }
}
